package com.leetcode;

/**
 * 1138. 字母板上的路径
 *
 * 我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。
 * 在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]，如下所示。
 *
 * 我们可以按下面的指令规则行动：
 * 如果方格存在，'U' 意味着将我们的位置上移一行；
 * 如果方格存在，'D' 意味着将我们的位置下移一行；
 * 如果方格存在，'L' 意味着将我们的位置左移一列；
 * 如果方格存在，'R' 意味着将我们的位置右移一列；
 * '!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。
 * （注意，字母板上只存在有字母的位置。）
 *
 * 返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。
 */
public class LeetCode1138 {

    public static void main(String[] arg0) {
        System.out.println("指令序列 = " + alphabetBoardPath("leetcode"));
    }

    public static String alphabetBoardPath(String target)  {
        StringBuilder res = new StringBuilder();

        char[] c = target.toCharArray();
        String op; // 操作 'U'，'D'，'L'，'R'
        int min, max;
        int hang = 0; // 记录上一个字母的行号，起始是a，对应行号为0
        int lie = 0; // 记录上一个字母的列号，起始是a，对应行列为0

        for (int i = 0; i < c.length; i++) {
            char curr = c[i];
            int diff = curr - 'a';
            int currHang = diff / 5;
            int currLie = diff % 5;

            if (currLie == lie && currHang == hang) {
                res.append("!");
            } else {
                if (currHang == 5) { // curr 是 z，先拼列，后拼行
                    if (currLie != lie) { // currLie 一定是0
                        op = "L";
                        min = 0;
                        max = lie;
                    } else {
                        op = "";
                        min = 0;
                        max = 0;
                    }
                    for (int j = min; j < max; j++) {
                        res.append(op);
                    }
                    if (currHang != hang) {
                        op = "D";
                        min = hang;
                        max = currHang;
                        for (int j = min; j < max; j++) {
                            res.append(op);
                        }
                    }
                } else { // 其它情况都先上下移行，再左右移列
                    op = currHang >= hang ? "D" : "U";
                    min = Math.min(currHang, hang);
                    max = Math.max(currHang, hang);
                    for (int j = min; j < max; j++) {
                        res.append(op);
                    }

                    op = currLie >= lie ? "R" : "L";
                    min = Math.min(currLie, lie);
                    max = Math.max(currLie, lie);
                    for (int j = min; j < max; j++) {
                        res.append(op);
                    }
                }
                res.append("!");
            }
            hang = currHang;
            lie = currLie;
        }

        return res.toString();
    }

}
